package com.tgy.leetcode;

import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/8/20 9:43 AM
 *
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 */
public class _106_从中序与后序遍历序列构造二叉树_02 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        if (inorder == null || postorder == null || inorder.length != postorder.length ) {

            return null;
        }

        if (inorder.length == 0) {

            return null;
        }

        return generate(inorder,0,inorder.length - 1,postorder,0,postorder.length - 1);
    }

    private TreeNode generate(int[] inorder, int inLeft, int inRight, int[] postoder, int postLeft,int postRight) {

        // 注意，这个大于返回null
        if (postLeft > postRight) {

            return null;
        }

        if (postLeft == postRight) {

            return new TreeNode(postoder[postLeft]);
        }



        int rootVal = postoder[postRight];
        TreeNode root = new TreeNode(rootVal);
        int index = indexOfVal(inorder, rootVal);

        root.left = generate(inorder,inLeft,index -1,postoder,postLeft,postRight - inRight + index - 1);
        root.right = generate(inorder,index+1,inRight,postoder,postRight - inRight + index,postRight-1);

        return root;
    }

    private int indexOfVal(int[] vals,int val) {

        for (int i = 0; i < vals.length; i++) {

            if (vals[i] == val){

                return i;
            }
        }
        return -1;
    }
}
